home *** CD-ROM | disk | FTP | other *** search
/ InterCD 2000 September / september_2000.iso / intercd / root / ^Linux / cdrtools-1.10 / libhfs_iso / node.c < prev    next >
Encoding:
C/C++ Source or Header  |  2000-03-05  |  9.6 KB  |  491 lines
  1. /*
  2.  * hfsutils - tools for reading and writing Macintosh HFS volumes
  3.  * Copyright (C) 1996, 1997 Robert Leslie
  4.  *
  5.  * This program is free software; you can redistribute it and/or modify
  6.  * it under the terms of the GNU General Public License as published by
  7.  * the Free Software Foundation; either version 2 of the License, or
  8.  * (at your option) any later version.
  9.  *
  10.  * This program is distributed in the hope that it will be useful,
  11.  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  12.  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13.  * GNU General Public License for more details.
  14.  *
  15.  * You should have received a copy of the GNU General Public License
  16.  * along with this program; if not, write to the Free Software
  17.  * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  18.  */
  19.  
  20. #include <mconfig.h>
  21. #include <stdxlib.h>
  22. #include <strdefs.h>
  23. #include <errno.h>
  24.  
  25. #include "internal.h"
  26. #include "data.h"
  27. #include "btree.h"
  28. #include "node.h"
  29.  
  30. # define NODESPACE(n)  \
  31.   (HFS_BLOCKSZ - (n).roff[(n).nd.ndNRecs] - 2 * ((n).nd.ndNRecs + 1))
  32.  
  33. /*
  34.  * NAME:    node->init()
  35.  * DESCRIPTION:    construct an empty node
  36.  */
  37. void n_init(np, bt, type, height)
  38.     node    *np;
  39.     btree    *bt;
  40.     int    type;
  41.     int    height;
  42. {
  43.   np->bt   = bt;
  44.   np->nnum = -1;
  45.  
  46.   np->nd.ndFLink   = 0;
  47.   np->nd.ndBLink   = 0;
  48.   np->nd.ndType    = type;
  49.   np->nd.ndNHeight = height;
  50.   np->nd.ndNRecs   = 0;
  51.   np->nd.ndResv2   = 0;
  52.  
  53.   np->rnum    = -1;
  54.   np->roff[0] = 0x00e;
  55.  
  56.   memset(np->data, 0, sizeof(np->data));
  57. }
  58.  
  59. /*
  60.  * NAME:    node->new()
  61.  * DESCRIPTION:    allocate a new b*-tree node
  62.  */
  63. int n_new(np)
  64.     node    *np;
  65. {
  66.   btree *bt = np->bt;
  67.   unsigned long num;
  68.  
  69.   if (bt->hdr.bthFree == 0)
  70.     {
  71.       ERROR(EIO, "b*-tree full");
  72.       return -1;
  73.     }
  74.  
  75.   num = 0;
  76.   while (num < bt->hdr.bthNNodes && BMTST(bt->map, num))
  77.     ++num;
  78.  
  79.   if (num == bt->hdr.bthNNodes)
  80.     {
  81.       ERROR(EIO, "free b*-tree node not found");
  82.       return -1;
  83.     }
  84.  
  85.   np->nnum = num;
  86.  
  87.   BMSET(bt->map, num);
  88.   --bt->hdr.bthFree;
  89.  
  90.   bt->flags |= HFS_UPDATE_BTHDR;
  91.  
  92.   return 0;
  93. }
  94.  
  95. /*
  96.  * NAME:    node->free()
  97.  * DESCRIPTION:    deallocate a b*-tree node
  98.  */
  99. void n_free(np)
  100.     node    *np;
  101. {
  102.   btree *bt = np->bt;
  103.  
  104.   BMCLR(bt->map, np->nnum);
  105.   ++bt->hdr.bthFree;
  106.  
  107.   bt->flags |= HFS_UPDATE_BTHDR;
  108. }
  109.  
  110. /*
  111.  * NAME:    node->compact()
  112.  * DESCRIPTION:    clean up a node, removing deleted records
  113.  */
  114. void n_compact(np)
  115.     node    *np;
  116. {
  117.   unsigned char *ptr;
  118.   int offset, nrecs, i;
  119.  
  120.   offset = 0x00e;
  121.   ptr    = np->data + offset;
  122.   nrecs  = 0;
  123.  
  124.   for (i = 0; i < np->nd.ndNRecs; ++i)
  125.     {
  126.       unsigned char *rec;
  127.       int reclen;
  128.  
  129.       rec    = HFS_NODEREC(*np, i);
  130.       reclen = np->roff[i + 1] - np->roff[i];
  131.  
  132.       if (HFS_RECKEYLEN(rec) > 0)
  133.     {
  134.       np->roff[nrecs++] = offset;
  135.       offset += reclen;
  136.  
  137.       if (ptr == rec)
  138.         ptr += reclen;
  139.       else
  140.         {
  141.           while (reclen--)
  142.         *ptr++ = *rec++;
  143.         }
  144.     }
  145.     }
  146.  
  147.   np->roff[nrecs] = offset;
  148.   np->nd.ndNRecs  = nrecs;
  149. }
  150.  
  151. /*
  152.  * NAME:    node->search()
  153.  * DESCRIPTION:    locate a record in a node, or the record it should follow
  154.  */
  155. int n_search(np, key)
  156.     node        *np;
  157.     unsigned char    *key;
  158. {
  159.   btree *bt = np->bt;
  160.   int i, comp = -1;
  161.  
  162.   for (i = np->nd.ndNRecs; i--; )
  163.     {
  164.       unsigned char *rec;
  165.  
  166.       rec = HFS_NODEREC(*np, i);
  167.  
  168.       if (HFS_RECKEYLEN(rec) == 0)
  169.     continue;  /* deleted record */
  170.  
  171.       comp = bt->compare(rec, key);
  172.  
  173.       if (comp <= 0)
  174.     break;
  175.     }
  176.  
  177.   np->rnum = i;
  178.  
  179.   return comp == 0;
  180. }
  181.  
  182. /*
  183.  * NAME:    node->index()
  184.  * DESCRIPTION:    create an index record from a key and node pointer
  185.  */
  186. void n_index(bt, key, nnum, record, reclen)
  187.     btree        *bt;
  188.     unsigned char    *key;
  189.     unsigned long    nnum;
  190.     unsigned char    *record;
  191.     int        *reclen;
  192. {
  193.   if (bt == &bt->f.vol->cat)
  194.     {
  195.       /* force the key length to be 0x25 */
  196.  
  197.       HFS_RECKEYLEN(record) = 0x25;
  198.       memset(record + 1, 0, 0x25);
  199.       memcpy(record + 1, key + 1, HFS_RECKEYLEN(key));
  200.     }
  201.   else
  202.     memcpy(record, key, HFS_RECKEYSKIP(key));
  203.  
  204.   d_putl(HFS_RECDATA(record), nnum);
  205.  
  206.   if (reclen)
  207.     *reclen = HFS_RECKEYSKIP(record) + 4;
  208. }
  209.  
  210. /*
  211.  * NAME:    node->split()
  212.  * DESCRIPTION:    divide a node into two and insert a record
  213.  */
  214. int n_split(left, record, reclen)
  215.     node        *left;
  216.     unsigned char    *record;
  217.     int        *reclen;
  218. {
  219.   node right;
  220.   int nrecs, i, mid;
  221.   unsigned char *rec;
  222.  
  223.   right = *left;
  224.   right.nd.ndBLink = left->nnum;
  225.  
  226.   if (n_new(&right) < 0)
  227.     return -1;
  228.  
  229.   left->nd.ndFLink = right.nnum;
  230.   nrecs = left->nd.ndNRecs;
  231.  
  232.   /*
  233.    * Ensure node split leaves enough room for new record.
  234.    * The size calculations used are based on the NODESPACE() macro, but
  235.    * I don't know what the extra 2's and 1's are needed for.
  236.    * John Witford <jwitford@hutch.com.au>
  237.    */
  238.   n_search(&right, record);
  239.   mid = nrecs/2;
  240.   for(;;)
  241.     {
  242.     if (right.rnum < mid)
  243.     {
  244.         if (   mid > 0
  245.         && left->roff[mid] + *reclen + 2 > HFS_BLOCKSZ - 2 * (mid + 1))
  246.         {
  247.         --mid;
  248.         if (mid > 0)
  249.             continue;
  250.         }
  251.     }
  252.     else
  253.     {
  254.         if (   mid < nrecs
  255.         && right.roff[nrecs] - right.roff[mid] + left->roff[0] + *reclen + 2 > HFS_BLOCKSZ - 2 * (mid + 1))
  256.         {
  257.         ++mid;
  258.         if (mid < nrecs)
  259.             continue;
  260.         }
  261.     }
  262.     break;
  263.     }
  264.  
  265.   for (i = 0; i < nrecs; ++i)
  266.     {
  267.     if (i < mid)
  268.         rec = HFS_NODEREC(right, i);
  269.     else
  270.         rec = HFS_NODEREC(*left, i);
  271.  
  272.     HFS_RECKEYLEN(rec) = 0;
  273.     }
  274.  
  275. /* original code ...
  276.   for (i = 0; i < nrecs; ++i)
  277.     {
  278.       if (i < nrecs / 2)
  279.     rec = HFS_NODEREC(right, i);
  280.       else
  281.     rec = HFS_NODEREC(*left, i);
  282.  
  283.       HFS_RECKEYLEN(rec) = 0;
  284.     }
  285. */
  286.   n_compact(left);
  287.   n_compact(&right);
  288.  
  289.   n_search(&right, record);
  290.   if (right.rnum >= 0)
  291.     n_insertx(&right, record, *reclen);
  292.   else
  293.     {
  294.       n_search(left, record);
  295.       n_insertx(left, record, *reclen);
  296.     }
  297.  
  298.   /* store the new/modified nodes */
  299.  
  300.   if (bt_putnode(left) < 0 ||
  301.       bt_putnode(&right) < 0)
  302.     return -1;
  303.  
  304.   /* create an index record for the new node in the parent */
  305.  
  306.   n_index(right.bt, HFS_NODEREC(right, 0), right.nnum, record, reclen);
  307.  
  308.   /* update link pointers */
  309.  
  310.   if (left->bt->hdr.bthLNode == left->nnum)
  311.     {
  312.       left->bt->hdr.bthLNode = right.nnum;
  313.       left->bt->flags |= HFS_UPDATE_BTHDR;
  314.     }
  315.  
  316.   if (right.nd.ndFLink)
  317.     {
  318.       node n;
  319.  
  320.       n.bt   = right.bt;
  321.       n.nnum = right.nd.ndFLink;
  322.  
  323.       if (bt_getnode(&n) < 0)
  324.     return -1;
  325.  
  326.       n.nd.ndBLink = right.nnum;
  327.  
  328.       if (bt_putnode(&n) < 0)
  329.     return -1;
  330.     }
  331.  
  332.   return 0;
  333. }
  334.  
  335. /*
  336.  * NAME:    node->insertx()
  337.  * DESCRIPTION:    insert a record into a node (which must already have room)
  338.  */
  339. void n_insertx(np, record, reclen)
  340.     node        *np;
  341.     unsigned char    *record;
  342.     int        reclen;
  343. {
  344.   int rnum, i;
  345.   unsigned char *ptr;
  346.  
  347.   rnum = np->rnum + 1;
  348.  
  349.   /* push other records down to make room */
  350.  
  351.   for (ptr = HFS_NODEREC(*np, np->nd.ndNRecs) + reclen;
  352.        ptr > HFS_NODEREC(*np, rnum) + reclen; --ptr)
  353.     *(ptr - 1) = *(ptr - 1 - reclen);
  354.  
  355.   ++np->nd.ndNRecs;
  356.  
  357.   for (i = np->nd.ndNRecs; i > rnum; --i)
  358.     np->roff[i] = np->roff[i - 1] + reclen;
  359.  
  360.   /* write the new record */
  361.  
  362.   memcpy(HFS_NODEREC(*np, rnum), record, reclen);
  363. }
  364.  
  365. /*
  366.  * NAME:    node->insert()
  367.  * DESCRIPTION:    insert a new record into a node; return a record for parent
  368.  */
  369. int n_insert(np, record, reclen)
  370.     node        *np;
  371.     unsigned char    *record;
  372.     int        *reclen;
  373. {
  374.   n_compact(np);
  375.  
  376.   /* check for free space */
  377.  
  378.   if (np->nd.ndNRecs >= HFS_MAXRECS ||
  379.       *reclen + 2 > NODESPACE(*np))
  380.     return n_split(np, record, reclen);
  381.  
  382.   n_insertx(np, record, *reclen);
  383.   *reclen = 0;
  384.  
  385.   return bt_putnode(np);
  386. }
  387.  
  388. /*
  389.  * NAME:    node->merge()
  390.  * DESCRIPTION:    combine two nodes into a single node
  391.  */
  392. int n_merge(right, left, record, flag)
  393.     node        *right;
  394.     node        *left;
  395.     unsigned char    *record;
  396.     int        *flag;
  397. {
  398.   int i, offset;
  399.  
  400.   /* copy records and offsets */
  401.  
  402.   memcpy(HFS_NODEREC(*left, left->nd.ndNRecs), HFS_NODEREC(*right, 0),
  403.      right->roff[right->nd.ndNRecs] - right->roff[0]);
  404.  
  405.   offset = left->roff[left->nd.ndNRecs] - right->roff[0];
  406.  
  407.   for (i = 1; i <= right->nd.ndNRecs; ++i)
  408.     left->roff[++left->nd.ndNRecs] = offset + right->roff[i];
  409.  
  410.   /* update link pointers */
  411.  
  412.   left->nd.ndFLink = right->nd.ndFLink;
  413.  
  414.   if (bt_putnode(left) < 0)
  415.     return -1;
  416.  
  417.   if (right->bt->hdr.bthLNode == right->nnum)
  418.     {
  419.       right->bt->hdr.bthLNode = left->nnum;
  420.       right->bt->flags |= HFS_UPDATE_BTHDR;
  421.     }
  422.  
  423.   if (right->nd.ndFLink)
  424.     {
  425.       node n;
  426.  
  427.       n.bt   = right->bt;
  428.       n.nnum = right->nd.ndFLink;
  429.  
  430.       if (bt_getnode(&n) < 0)
  431.     return -1;
  432.  
  433.       n.nd.ndBLink = left->nnum;
  434.  
  435.       if (bt_putnode(&n) < 0)
  436.     return -1;
  437.     }
  438.  
  439.   n_free(right);
  440.  
  441.   HFS_RECKEYLEN(record) = 0;
  442.   *flag = 1;
  443.  
  444.   return 0;
  445. }
  446.  
  447. /*
  448.  * NAME:    node->delete()
  449.  * DESCRIPTION:    remove a record from a node
  450.  */
  451. int n_delete(np, record, flag)
  452.     node        *np;
  453.     unsigned char    *record;
  454.     int        *flag;
  455.  
  456. {
  457.   node left;
  458.   unsigned char *rec;
  459.  
  460.   rec = HFS_NODEREC(*np, np->rnum);
  461.  
  462.   HFS_RECKEYLEN(rec) = 0;
  463.   n_compact(np);
  464.  
  465.   /* see if we can merge with our left sibling */
  466.  
  467.   left.bt   = np->bt;
  468.   left.nnum = np->nd.ndBLink;
  469.  
  470.   if (left.nnum > 0)
  471.     {
  472.       if (bt_getnode(&left) < 0)
  473.     return -1;
  474.  
  475.       if (np->nd.ndNRecs + left.nd.ndNRecs <= HFS_MAXRECS &&
  476.       np->roff[np->nd.ndNRecs] - np->roff[0] +
  477.       2 * np->nd.ndNRecs <= NODESPACE(left))
  478.     return n_merge(np, &left, record, flag);
  479.     }
  480.  
  481.   if (np->rnum == 0)
  482.     {
  483.       /* special case: first record changed; update parent record key */
  484.  
  485.       n_index(np->bt, HFS_NODEREC(*np, 0), np->nnum, record, 0);
  486.       *flag = 1;
  487.     }
  488.  
  489.   return bt_putnode(np);
  490. }
  491.